package lcof;

import java.util.*;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: Permutation38
 * @description: 输入一个字符串，打印出该字符串中字符的所有排列。
 *
 *  
 *
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
 *
 *  
 *
 * 示例:
 *
 * 输入：s = "abc"
 * 输出：["abc","acb","bac","bca","cab","cba"]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/5/1116:19
 * @since V1.0
 */
public class Permutation38 {
    Set<String> res;

    public String[] permutation(String s) {
        res =  new HashSet<String>();
        ArrayList<Character> chars = new ArrayList<>();
        for (char c:s.toCharArray()){
            chars.add(c);
        }
        bfs("",chars);
        return   res.toArray(new String[0]);
    }

    public void bfs(String temp,List<Character> chars){
        if (chars.size()==0){
            res.add(temp.toString());
            return;
        }
        for (Character c:chars){
            temp = temp + c;
            List<Character> list = new ArrayList<>(chars);
            list.remove(c);
            bfs(temp,list);
            temp =  temp.substring(0, temp.length() - 1);
        }
    }

    public static void main(String[] args) {

        System.out.println(Arrays.toString(new Permutation38().permutation("aba")));
//        String s = "abc";
//        System.out.println(s);
//        s.substring(0, 1);
//        System.out.println(s);


    }

    class Solution {
        List<String> res = new LinkedList<>();
        char[] c;
        public String[] permutation(String s) {
            c = s.toCharArray();
            dfs(0);
            return res.toArray(new String[res.size()]);
        }
        void dfs(int x) {
            if(x == c.length - 1) {
                res.add(String.valueOf(c));      // 添加排列方案
                return;
            }
            HashSet<Character> set = new HashSet<>();
            for(int i = x; i < c.length; i++) {
                if(set.contains(c[i])) continue; // 重复，因此剪枝
                set.add(c[i]);
                swap(i, x);                      // 交换，将 c[i] 固定在第 x 位
                dfs(x + 1);                      // 开启固定第 x + 1 位字符
                swap(i, x);                      // 恢复交换
            }
        }
        void swap(int a, int b) {
            char tmp = c[a];
            c[a] = c[b];
            c[b] = tmp;
        }
    }

}

